//给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
//
//
//
// 示例 1：
//
//
//
//
//输入：root = [3,9,20,null,null,15,7]
//输出：[3.00000,14.50000,11.00000]
//解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
//因此返回 [3, 14.5, 11] 。
//
//
// 示例 2:
//
//
//
//
//输入：root = [3,9,20,15,7]
//输出：[3.00000,14.50000,11.00000]
//
//
//
//
// 提示：
//
//
//
//
// 树中节点数量在 [1, 104] 范围内
// -231 <= Node.val <= 231 - 1
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树
// 👍 464 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        double sum = 0.0, avg = 0.0;
        Deque<TreeNode> que = new LinkedList<>();
        que.addLast(root);
        while (!que.isEmpty()) {
            //返回当前层所添加的元素数
            int levelSize = que.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode tmp = que.pollFirst();

                if (tmp.left != null)
                    que.add(tmp.left);
                if (tmp.right != null)
                    que.add(tmp.right);
                sum += tmp.val;
            }
            avg = sum / levelSize;
            resList.add(avg);
            // 最后要记得清零才可以，每层加完之后要清零才行
            sum = 0.0;
        }
        return resList;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
